package a04_字符串;

/**
 * <p>
 * a07_重复的子字符串复习5
 * </p>
 *
 * @author flyduck
 * @since 2025/4/24
 */
public class a07_重复的子字符串复习5 {
    public static void main(String[] args) {
        a07_重复的子字符串复习5 test = new a07_重复的子字符串复习5();
        System.out.println(test.repeatedSubstringPattern("abab"));
    }
    //abcabcabcabc
    //            9
    public boolean repeatedSubstringPattern(String s) {
        char[] chars = s.toCharArray();
        int[] nextArray = getNextArray(chars);
        if(nextArray[nextArray.length-1] == 0){
            return false;
        }
        return nextArray[nextArray.length-1] % (chars.length - nextArray[nextArray.length-1]) ==0;
    }

    private int[] getNextArray(char[] chars){
        if (chars.length == 1) {
            return new int[]{-1,0};
        }

        int[] nextArray = new int[chars.length + 1];
        nextArray[0] = -1;
        nextArray[1] = 0;
        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx-1];

        while (currentIdx < nextArray.length){
            if(chars[currentIdx-1] == chars[compareIdx]){
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx-1];
            }else {
                if(compareIdx == 0){
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx-1];
                }else {
                    compareIdx = nextArray[compareIdx];
                }
            }
        }
        return nextArray;
    }
}
